//
// Created by weslywang on 2020/5/10.
//


#include "../common/common.h"

struct PathNode {
    string val;
    vector<PathNode *> next;

    PathNode(string val) : val(val), next(NULL) {}
};

string toString(vector<string> str) {
    string s = "";
    for (int i = 0; i < str.size(); i++) {
        s += str[i] + ",";
    }
    return s;
}

string toString2(map<string, int> current) {
    string s = "";
    map<string, int>::iterator iter;
    for (iter = current.begin(); iter != current.end(); iter++) {
        s += iter->first + ",";
    }
    return s;
}

string toString3(map<string, vector<string>> current) {
    string s = "";
    map<string, vector<string>>::iterator iter;
    for (iter = current.begin(); iter != current.end(); iter++) {
        s += iter->first + ": " + toString(iter->second);
    }
    return s;
}

string toString4(vector<PathNode *> current) {
    string s = "";
    for (int i = 0; i < current.size(); i++) {
        s += current[i]->val + ", ";
    }
    return s;
}

void printMap(map<string, vector<string>> mmap) {
    map<string, vector<string>>::iterator iter;
    for (iter = mmap.begin(); iter != mmap.end(); iter++) {
        cout << iter->first << ": " << toString(iter->second) << endl;
    }
}

void printVector(vector<vector<string>> mmap) {
    for (int i = 0; i < mmap.size(); i++) {
        cout << "结果" << (i + 1) << ": " << toString(mmap[i]) << endl;
    }
}

bool isLike(string s1, string s2) {
    int dif = 0;
    for (int i = 0; i < s1.size(); i++) {
        if (s1[i] != s2[i]) {
            dif++;
        }
        if (dif > 1) {
            break;
        }
    }
    return dif == 1 ? true : false;
}

bool containes(vector<string> &path, string &str) {
    for (int i = 0; i < path.size(); i++) {
        if (path[i] == str) {
            return true;
        }
    }
    return false;
}

bool
calc(string endWord, map<string, vector<string>> mymap, vector<PathNode *> currentLevel, map<string, int> used,
     vector<string> &wordList) {
    vector<PathNode *> nextLevel;
    int num = 0;//本次 BFS 新加入几个字符串
    bool isFind = false;
//    vector<string> store;
//    cout << "当前：" << toString4(currentLevel) << endl;
    for (int i = 0; i < currentLevel.size(); i++) {
        if (currentLevel[i]->val == endWord) {
            isFind = true;
        }
        vector<PathNode *> next;
//        findLikes2(currentLevel[i]->val, wordList, store);
        vector<string> store = mymap[currentLevel[i]->val];
//        vector<string> store = findLikes(currentLevel[i]->val, wordList, mymap);
        for (int k = 0; k < store.size(); k++) {
            if (used[store[k]] == 1 && store[k] != endWord) {
                continue;
            }
            if (store[k] == endWord) {
                isFind = true;
            }
            num++;
            PathNode *node = new PathNode(store[k]);
            nextLevel.push_back(node);
            next.push_back(node);
        }
        currentLevel[i]->next = next;
    }
    if (isFind) {
        return true;
    } else if (num == 0) {
        return false;
    } else {
        for (int i = 0; i < nextLevel.size(); i++) {
            used[nextLevel[i]->val] = 1;
        }
        return calc(endWord, mymap, nextLevel, used, wordList);
    }
}

void formatResult(string &endWord, vector<vector<string>> &result, vector<PathNode *> &currentLevel, vector<string> &pre) {
    for (int i = 0; i < currentLevel.size(); i++) {
        vector<string> tmp(pre);
        tmp.push_back(currentLevel[i]->val);
        if (currentLevel[i]->next.size() == 0 && currentLevel[i]->val == endWord) {
            result.push_back(tmp);
        } else {
            formatResult(endWord, result, currentLevel[i]->next, tmp);
        }
    }
}

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {
    vector<string> pre;
    struct timeval start;
    struct timeval end;
    unsigned long timer;

    map<string, vector<string>> mymap;
    vector<vector<string>> result;
    map<string, map<string, int>> likeMap;

    if (!containes(wordList, endWord)) {
        return result;
    }
    gettimeofday(&start, NULL);
    // 预处理
    if (!containes(wordList, beginWord)) {
        wordList.push_back(beginWord);
    }
    // 方法1
    for (int i = 0; i < wordList.size() - 1; i++) {
        vector<string> row;
        for (int k = i + 1; k < wordList.size(); k++) {
            if (isLike(wordList[i], wordList[k])) {
                row.push_back(wordList[k]);
                if (mymap[wordList[k]].size() > 0) {
                    vector<string> row2 = mymap[wordList[k]];
                    row2.push_back(wordList[i]);
                    mymap[wordList[k]] = row2;
                } else {
                    vector<string> row2;
                    row2.push_back(wordList[i]);
                    mymap[wordList[k]] = row2;
                }
            }
        }

        vector<string> row3 = mymap[wordList[i]];
        for (int i = 0; i < row.size(); i++) {
            row3.push_back(row[i]);
        }
        mymap[wordList[i]] = row3;
    }

    // 方法3
//    for (int i = 0; i < wordList.size(); i++) {
//        vector<string> row;
//        for (int k = 0; k < wordList.size(); k++) {
//            if (isLike(wordList[i], wordList[k])) {
//                row.push_back(wordList[k]);
//            }
//        }
//        mymap[wordList[i]] = row;
//    }

    gettimeofday(&end, NULL);
    timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
    cout << timer / 1000 << " 预处理毫秒" << endl;

//    printMap(mymap);
    vector<PathNode *> currentLevel;
    map<string, int> used;
    PathNode *node = new PathNode(beginWord);
    currentLevel.push_back(node);
    used[beginWord] = 1;

//    gettimeofday(&start, NULL);
    bool isFind = calc(endWord, mymap, currentLevel, used, wordList);
//    gettimeofday(&end, NULL);
    timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
//    cout << timer / 1000 << " calc毫秒" << endl;

    if (isFind) {

//        gettimeofday(&start, NULL);

        formatResult(endWord, result, currentLevel, pre);

//        gettimeofday(&end, NULL);
        timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
//        cout << timer / 1000 << " formatResult毫秒" << endl;
    }
    return result;
}

vector<vector<string>> findLadders2(string beginWord, string endWord, vector<string>& wordList) {
    vector<vector<string>> res;
    unordered_set<string> dict(wordList.begin(), wordList.end());
    vector<string> p{beginWord};
    queue<vector<string>> paths;
    paths.push(p);
    int level = 1, minLevel = INT_MAX;
    unordered_set<string> words;
    while (!paths.empty()) {
        auto t = paths.front(); paths.pop();
        if (t.size() > level) {
            for (string w : words) dict.erase(w);
            words.clear();
            level = t.size();
            if (level > minLevel) break;
        }
        string last = t.back();
        for (int i = 0; i < last.size(); ++i) {
            string newLast = last;
            for (char ch = 'a'; ch <= 'z'; ++ch) {
                newLast[i] = ch;
                if (!dict.count(newLast)) continue;
                words.insert(newLast);
                vector<string> nextPath = t;
                nextPath.push_back(newLast);
                if (newLast == endWord) {
                    res.push_back(nextPath);
                    minLevel = level;
                } else paths.push(nextPath);
            }
        }
    }
    return res;
}

int main() {
    struct timeval start;
    struct timeval end;
    unsigned long timer;

    Common common;
    int a[] = {1, 2, 3, 4, 5};
    vector<vector<string>> numList = common.loadStringData();
    for (int i = 0; i < numList.size(); i++) {
        gettimeofday(&start, NULL);

//        auto index = find(numList[i].begin(), numList[i].end(), "grind1");
//        if (index != numList[i].end()) {
//            cout << "找到了" << endl;
//        }
//        cout<<index<<endl;

//        printVector(findLadders("qa", "sq", numList[i]));
//        printVector(findLadders("a", "c", numList[i]));
//        printVector(findLadders("hit", "cog", numList[i]));
//        printVector(findLadders("hot", "dog", numList[i]));
//        printVector(findLadders("cet", "ism", numList[i]));
//        printVector(findLadders("sand", "acne", numList[i]));
        printVector(findLadders("nanny", "aloud", numList[i]));

        gettimeofday(&end, NULL);
        timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
        cout << timer / 1000 << "毫秒" << endl;
        cout << "**************" << endl;
    }
    return 0;
}